package com.kaifamiao.month03.day0321;

public class QuickSort {

    public static void main(String[] args) {
        int[] nums = {1, 2, 56, 52, 54, 23, 0};
        quickSort(nums,0, nums.length - 1);
        print(nums);
    }

    /**
     * 获取中间的下标
     * @param nums 排序的数组
     * @param low 低位
     * @param high 高位
     * @return 返回本轮确定的数字的位置
     */
    public static int getMid(int[] nums, int low, int high){
        int temp = nums[low]; // 自定义一个中间的数字
        while(low < high){
            // 如果数字比自定义的中间的数字小，放到左边
            while(nums[high] >= temp && low < high){
                high --;
            }
            nums[low] = nums[high];
            // 如果数字比最后一位的数字大，放到右边
            while(nums[low] <= temp && low < high){
                low ++;
            }
            nums[high] = nums[low];
        }
        nums[low] = temp; // 每次确定的位置
        return low; // 返回每次确定的一个数字的下标
    }

    public static void quickSort(int[] nums , int low , int high){
        if(low < high){
            int mid = getMid(nums, low, high);
            quickSort(nums, low ,mid -1);
            quickSort(nums, mid + 1, high);
        }
    }

    public static void print(int[] nums){
        for (int n : nums ) {
            System.out.print(n + "\t");
        }
    }
}
